package com.asa.jihe;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;

import com.asa.jihe.utils.Line;
import com.asa.jihe.utils.Point;
import com.asa.jihe.utils.ToLeftTest;


/**
 * 相交线
 * 判断一个平面上面，是否有相交的线段
 * 有点写不动
 * @author asa
 *
 */
public class JiHeQiuJiao {
	
	
	
	
	
	
	public static void main(String[] args) {
		List<Point> pointlist = initpointtolist();
		
		
//		List<Point> sortx = sortx(pointlist);
//		
//		
//		for (int i = 0; i < sortx.size(); i++) {
//			System.out.println(sortx.get(i).x);
//		}
		
		
		
		List<Line> linelist = initlinetolist(pointlist);
		
		List<Integer> result2 = jiaochaxian(linelist);
		

		
		
		//课程中介绍的比较推崇的方法是扫描法，这种方法要求的是平面大小是确定的，我感觉那个不是很给力
		//我不如先对线的起始点进行定义排序，使得总是有x比较小的起点到x比较大的终点的线
		//这样我就遍历出可能的交叉线，对其进行判断即可
		
		
		List<Integer[]> result = jiaochaxian2(pointlist,linelist);
		
		
		
		
		System.out.println("          "+result2.size());
		
		for (int i = 0; i < result2.size(); i+=2) {
			System.out.println(result2.get(i)+ "            "+result2.get(i+1));
		}
		System.out.println("=============================================================");
		System.out.println(result.size());
		for (int i = 0; i < result.size(); i++) {
			System.out.println(result.get(i)[0]+ "     "+result.get(i)[1]);
		}

		
		System.out.println(linelist.get(4));
		System.out.println(linelist.get(3));

		
		System.out.println(linelist.get(0));
		System.out.println(linelist.get(3));
		
		boolean jiaocha = jiaocha(linelist.get(0), linelist.get(3));
		boolean jiaocha2 = jiaocha(linelist.get(3), linelist.get(0));

		System.out.println(jiaocha);
		System.out.println(jiaocha2);

		
	}
	
	
	
	
	

	
	
	
	
	
	
	
	
	
	
	
	
	
	

	private static List<Integer[]> jiaochaxian2(List<Point> pointlist,List<Line> linelist) {
		
		
		for (int i = 0; i < linelist.size(); i++) {
			Line line = linelist.get(i);
			line.spoint.line = line;
			line.epoint.line = line;
			
			if (line.spoint.x>line.epoint.x) {//按x轴进行整合，使得开始点到结束点的向量
				Point pointbuff = line.spoint;
				line.spoint = line.epoint;
				line.epoint = pointbuff;
			}
			
		}

		
		
		
		
		List<Point> sortx = sortx(pointlist);
		
		for (int i = 0; i < sortx.size(); i++) {
//			System.out.println(sortx.get(i).x);
			System.out.println(sortx.get(i).line);

		}
		
		System.out.println("=========================");
		
//		List<Point> sorty = sorty(pointlist);
//
//		
//		for (int i = 0; i < sorty.size(); i++) {
////			System.out.println(sorty.get(i).y);
//			System.out.println(sorty.get(i).line);
//
//		}
		
		
		//我们还是来对这些点进行遍历，在这些点起点和终点包含其他点的情况就进行线的判断，原理就是，线段中包含的点的线，那么这些线就有可能是相交线
		//我们对这些有可能的点进行判断，那么，我们可以节约很多时间，这样我就有一个大胆的想法，为什么我们不再以y轴进行扫描呢？这想法想累死我吗？。。。所以不实现这种了
		List<Point> pointstack = new ArrayList<>();//我想了一会，这个东西是个栈结构，而且很跳
		List<Integer[]> result = new ArrayList<>();
		for (int i = 0; i < sortx.size(); i++) {

			Point point = sortx.get(i);
			Line line = point.line;
			System.out.println(point);
			System.out.println(line);
			System.out.println(pointstack.size());
			System.out.println("-----------------------------------");

			
			if (point==line.spoint) {//如果这个点是线段的起始点
				
				for (int j = 0; j < pointstack.size(); j++) {
					Point pointst = pointstack.get(j);
					Line linest = pointst.line;
					boolean jiaocha = jiaocha(linest, line);
					if (jiaocha) {//如果这两条线相交就记录下来
						Integer[] asa = new Integer[2];
						asa[0] = line.index;
						asa[1] = linest.index;

						result.add(asa);
					}
					
				}
				
				
				pointstack.add(point);//将起始点压如栈中
			}

			
			
			
			if (point==line.epoint) {//如果这个点是线段的终结点
				
				pointstack.remove(line.spoint);
				
				

			}

		}
		return result;
	}

	/**
	 * 找出平面上的交叉线，返回交叉了的线的index，两两一组
	 * @param linelist	线list
	 * @return
	 */
	private static List<Integer> jiaochaxian(List<Line> linelist) {
		List<Integer> result = new ArrayList<Integer>();
		
		
		for (int i = 0; i < linelist.size(); i++) {
			System.out.println(linelist.get(i));
		}
		
		
		
		for (int i = 0; i < linelist.size()-1; i++) {
			Line line1 = linelist.get(i);
			
			for (int j = i+1; j < linelist.size(); j++) {
				Line line2 = linelist.get(j);
				
				boolean jiaocha = jiaocha(line1, line2);
				if (jiaocha) {
					result.add(i);
					result.add(j);
				}
				

			}
			
		}
		return result;
	}

	/**
	 * 判断两条直线是否相交
	 * @param line1
	 * @param line2
	 * @return
	 */
	public static boolean jiaocha(Line line1,Line line2) {
		
		
		Point spoint1 = line1.spoint;
		Point epoint1 = line1.epoint;

		Point spoint2 = line2.spoint;
		Point epoint2 = line2.epoint;
		
		boolean x = false;
		
		if ((spoint2.x>spoint1.x&&spoint2.x>epoint1.x&&epoint2.x>spoint1.x&&epoint2.x>epoint1.x)||(spoint2.x<spoint1.x&&spoint2.x<epoint1.x&&epoint2.x<spoint1.x&&epoint2.x<epoint1.x)) {
			x = true;
		}
		
		boolean y = false;

		if ((spoint2.y>spoint1.y&&spoint2.y>epoint1.y&&epoint2.y>spoint1.y&&epoint2.y>epoint1.y)||(spoint2.y<spoint1.y&&spoint2.y<epoint1.y&&epoint2.y<spoint1.y&&epoint2.y<epoint1.y)) {
			y = true;
		}
		if (y||x) {
			return false;
		}
		
		
		
		boolean leftTest = ToLeftTest.toLeftTest(spoint2, spoint1, epoint1);
		boolean leftTest2 = ToLeftTest.toLeftTest(epoint2, spoint1, epoint1);
		
		boolean online1 = ToLeftTest.toOnLineTest(epoint2, spoint1, epoint1);//这个是为了防止三点在一条直线上的情况，如果三点在一条直线上那么也算相交，但我们应该可以让这个方法更有灵气点
		boolean online2 = ToLeftTest.toOnLineTest(spoint2, spoint1, epoint1);//这个是为了防止三点在一条直线上的情况，如果三点在一条直线上那么也算相交，但我们应该可以让这个方法更有灵气点

		
		
		return (leftTest!=leftTest2)||online1||online2;

//		return (leftTest!=leftTest2);
		
	}
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	/**
	 * 排序算法是可以进行优化到nlogn的
	 * @param points
	 * @return
	 */
	
	public static List<Point> sortx(List<Point> points){
		
		List<Point> pointcopys = new LinkedList<>();
		
		for (int i = 0; i < points.size(); i++) {
			pointcopys.add(points.get(i));
		}
		
		
		Collections.sort(pointcopys, new Comparator<Point>() {

			@Override
			public int compare(Point o1, Point o2) {
				// TODO Auto-generated method stub
				if (o1.x>o2.x) {
					return 1;
				}else if (o1.x<o2.x) {
					return -1;
				}
				
				
				return 0;
			}
		});
		return pointcopys;

		
	}
	
	
	public static List<Point> sorty(List<Point> points){
		List<Point> pointcopys = new LinkedList<>();
		for (int i = 0; i < points.size(); i++) {
			pointcopys.add(points.get(i));
		}		
		Collections.sort(pointcopys, new Comparator<Point>() {

			@Override
			public int compare(Point o1, Point o2) {
				// TODO Auto-generated method stub
				if (o1.y>o2.y) {
					return 1;
				}else if (o1.y<o2.y) {
					return -1;
				}

				return 0;
			}
		});
		return pointcopys;

	}
	
	
	
	private static List<Line> initlinetolist(List<Point> points) {
		List<Line> lines = new LinkedList<>();
		for (int i = 0; i < points.size(); i+=2) {
			Line line = new Line();
			line.spoint = points.get(i);
			line.epoint = points.get(i+1);
			line.index = i/2;
			lines.add(line);
		}
		
		
		
		
		return lines;
		
	}

	
	
	
	
	
	
	
	
	
	
	private static List<Point> initpointtolist() {
		Point[] points = new Point[10];
		
		points[0] = new Point();
		points[1] = new Point();
		points[2] = new Point();
		points[3] = new Point();
		points[4] = new Point();
		points[5] = new Point();
		points[6] = new Point();
		points[7] = new Point();
		points[8] = new Point();
		points[9] = new Point();
		
		//正方形的四个顶点
		points[2].x = 0;
		points[2].y = 0;
		points[7].x = 0;
		points[7].y = 2;
		points[4].x = 2;
		points[4].y = 2;
		points[6].x = 2;
		points[6].y = 0;
		
		
		points[0].x = 0.5;
		points[0].y = 1.5;
		points[3].x = 1.2;
		points[3].y = 1.2;
		points[5].x = 0.5;
		points[5].y = 1;
		points[1].x = 1;
		points[1].y = 0.5;
		points[8].x = 1;
		points[8].y = 1;
		
		points[9].x = 1;
		points[9].y = 4;
		
		
		
		List<Point> asList = new LinkedList<>();
		
		for (int i = 0; i < points.length; i++) {
			asList.add(points[i]);
		}
		
		
		return asList;
	}
	
	
	
	
	
	
	
	

}
